ＡＩ　ＳＬＯＢ　讓我們今天繼續：　ｌｅｔ’ｓ　ｇｏ～

Day 22、Day 23 解決的是評分：給定一份 layout，怎麼算 crossing counts 與 objective。

Day 24、Day 25 解決的是起點：怎麼用 force-directed method 產生一份比較有結構的 initial layout。

但一份不錯的起點不會自己變成答案。

從今天開始，我們要做搜尋：

current layout
      |
      | move one node
      v
candidate layout
      |
      | legal?
      | objective better?
      v
accept or reject

最直觀的做法是 hill climbing：candidate 比 current 好就接受，比 current 差就拒絕。

這個規則看起來非常合理，卻會讓搜尋很容易卡住。

今天要寫的是一條最普通、最容易驗證的 simulated annealing chain。它會故意保留一個看似不合理的能力：

有時接受比較差的 candidate。

一個簡化的 Local Minimum

先不看 graph，想像三個搜尋狀態：

objective 越小越好

state A: 4
state B: 5
state C: 2

allowed moves:
    A <-> B <-> C

我們目前位於 A：

        A
       4
      / \
     /   \      C
    /     B_____2
           5

C 才是最好的狀態，但 A 不能直接走到 C，必須先經過比較差的 B。

Hill climbing 在 A 看到：

candidate B = 5
current   A = 4

5 is worse than 4
    -> reject

它會永遠留在 A。

LCN 的 layout space 也有類似情況。移動一個 node 可能先讓某條 edge 多一個 crossing，才能在下一步把幾條嚴重交叉的 edges 一起解開。

current K = 4
    |
    | temporary detour
    v
candidate K = 5
    |
    | unlock another move
    v
later K = 2

Simulated annealing，縮寫 SA，允許第一個退步以一定機率發生。

SA 的核心只有五個動作

先看一條 chain 的完整骨架：

current = initial_layout
current_objective = evaluate(current)

best = copy(current)
best_objective = current_objective

temperature = start_temperature

for step in range(max_steps):
    candidate = propose(current)

    if not legal(candidate):
        temperature *= cooling
        continue

    candidate_objective = evaluate(candidate)

    if accept(current_objective,
              candidate_objective,
              temperature):
        current = candidate
        current_objective = candidate_objective

        if candidate_objective < best_objective:
            best = copy(candidate)
            best_objective = candidate_objective

    temperature *= cooling

反覆執行的五件事是：

1. propose 一個 move
2. 檢查 candidate 是否合法
3. 計算 candidate objective
4. 由溫度決定接受或拒絕
5. cooling

今天的版本一次只搬一個 node：

choose node v

old position = (x_old, y_old)
new position = (x_new, y_new)

all other node positions stay unchanged

這和 Day 23 的 incremental crossing 模型正好對上。只是為了建立可信 baseline，今天仍會完整複製 candidate、完整驗證、完整重算所有 edge pairs。

Current 和 Best 是兩份不同的狀態

SA 至少要保存兩份 layout：

current
    下一個 proposal 從哪裡出發
    允許暫時變差

best
    到目前為止看過的最好合法 layout
    只能被嚴格更好的 objective 更新

假設搜尋經過：

step 10
    current K = 4
    best K    = 4

step 11 accepts an uphill move
    current K = 5
    best K    = 4

step 12 finds a new basin
    current K = 3
    best K    = 3

如果每次接受較差解時也覆蓋 best，最後輸出可能比搜尋途中看過的答案更差。

反過來，如果每一步都從 best 出發，SA 剛接受的退步狀態根本沒有機會產生下一步：

accept B
reset current to A
    -> never reach C

所以 commit 規則必須分開：

if accepted:
    current = candidate

if current_objective < best_objective:
    best = copy(current)

current 由 stochastic acceptance 控制；best 由 strict lexicographic comparison 控制。

溫度到底控制什麼？

先用只有一個 scalar energy 的版本說明。

定義：

delta = candidate_energy - current_energy

因此：

delta < 0
    candidate better

delta = 0
    exact tie

delta > 0
    candidate worse

最基本的 Metropolis acceptance 是：

if delta <= 0:
    accept = True
else:
    probability = exp(-delta / temperature)
    accept = random_0_to_1() < probability

假設只退步一個單位：

delta = 1

不同溫度的接受機率是：

同一個 candidate 在高溫可能被接受，低溫則幾乎一定被拒絕。

溫度不是座標，也不是 graph 的物理溫度。它是搜尋願意承受多少 objective regression 的尺度。

Cooling：探索慢慢變成收斂

今天使用 geometric cooling：

temperature_at_step_t
    = start_temperature * cooling_rate ** t

程式寫成：

temperature *= cooling_rate

其中：

0 < cooling_rate < 1

例如：

start_temperature = 2.0
cooling_rate       = 0.999

step 0      -> T = 2.000000
step 1000   -> T is about 0.735
step 3000   -> T is about 0.0995
step 5000   -> T is about 0.0134

一開始比較敢跨過局部障礙，後面逐漸只接受改善。

Cooling 太快：

temperature quickly reaches almost zero
    -> behaves like hill climbing
    -> may freeze in the first basin

Cooling 太慢：

uphill moves remain common
    -> spends budget wandering
    -> best may improve, current may not settle

start_temperature 也不能脫離 energy scale 調整。若常見退步是 delta = 1000，T = 1 幾乎不會接受；若常見退步只有 delta = 0.001，相同溫度又會像完全隨機漫步。

LCN 不是只有一個 Scalar Objective

Day 21 定義的搜尋 objective 是：

objective = (K, n_K, Phi, C)

K   = max per-edge crossing count
n_K = number of edges whose count equals K
Phi = sum(count[e] * count[e])
C   = crossing pair count

保存 best 時可以直接做字典序比較：

smaller K wins
if K ties, smaller n_K wins
if both tie, smaller Phi wins
if all above tie, smaller C wins

例如：

current   = (4, 1, 40, 10)
candidate = (4, 2, 20,  8)

Candidate 的 Phi 和 C 比較小，但 n_K 從 1 變成 2。嚴格 lexicographic ranking 仍判定 candidate 比較差。

問題是 exp(-delta / T) 需要一個數字。Tuple 沒有自然的減法：

(4, 2, 20, 8) - (4, 1, 40, 10)

不能直接拿去做 exponential。

為什麼不能隨便乘上 1e12？

一個常見捷徑是：

energy = K   * 1e12
       + n_K * 1e6
       + Phi

它可以讓 scalar ranking 看起來接近 lexicographic order，卻會破壞溫度的可解釋性。

K worse by 1
    -> delta about 1e12

n_K worse by 1
    -> delta about 1e6

Phi worse by 1
    -> delta about 1

同一個 temperature 無法同時對三個量級提供合理的接受機率。調整 T 只是跟這些任意常數互相抵銷。

更危險的是，graph size 增加後 Phi 的範圍也會改變。原本足以隔開層級的 multiplier，可能不再足夠；再繼續放大又會面對 integer overflow 或 floating-point precision。

所以 production solver 把 ranking 與 stochastic search 分開：

best publication
    strict lexicographic tuple

current transition
    branch-aware acceptance energy

專案的 Layered Acceptance

今天的 sa_naive.py 依照 Flash-SA acceptance contract，逐層處理 objective。

第一層看 K：

delta_k = candidate.k - current.k

if delta_k < 0:
    accept
elif delta_k > 0:
    p = exp(-delta_k / T)
else:
    continue_to_secondary_objective()

K 相同時，先看 n_K。若 bottleneck edges 直接減少，就接受：

delta_n_k = candidate.n_k - current.n_k

if delta_n_k < 0:
    accept

其他情況把 n_K 和 Phi 組成 secondary delta：

unit = max(1, 2 * current.K - 1)

delta_secondary
    = delta_n_K * unit
    + delta_Phi

再依正負決定：

if delta_secondary < 0:
    accept
elif delta_secondary > 0:
    p = exp(-delta_secondary / (T * unit))

只有 secondary delta 相同時，才進入 C：

delta_C = candidate.C - current.C
scale   = T * max(1, current.C)

if delta_C < 0:
    accept
elif delta_C > 0:
    p = exp(-delta_C / scale)
else:
    reject exact tie

這裡的 unit = 2K - 1 是專案的搜尋尺度，不是所有 SA 都必須使用的數學常數。它讓 secondary branch 隨目前 K 調整。

也要注意，stochastic acceptance 不必維持 strict lexicographic monotonicity。它本來就允許 current 暫時變差。真正對外發布的 best 仍然只使用：

if candidate_objective < best_objective:
    publish_new_best()

Proposal 不是隨便丟一個座標就好

今天的 baseline proposal 很單純：

1. uniformly choose one node
2. uniformly choose one unoccupied interior grid point
3. keep every other node fixed

這個選擇有兩個好處。

第一，它容易驗證。只要固定 random seed，就能重播完全相同的 proposal sequence。

第二，forward 與 reverse proposal 的選擇空間相同。移動 node v 前後，排除其他 N - 1 個 occupied positions 後，可選的 free points 數量不變，因此基礎 Metropolis acceptance 不需要再乘 proposal ratio。

Production solver 會使用更聰明的 proposals，例如：

優先移動 max-K edge 的 endpoints
在 node 目前位置附近做 local move
往鄰居 centroid 移動
偶爾做 global jump

這些 proposals 可以更常碰到有價值的區域，卻也可能讓 forward 與 reverse probability 不再對稱。若要把它當成嚴格的 Metropolis-Hastings transition，就必須處理 proposal ratio。Day 28 講 parallel tempering 與 exchange 時會再回來看這個邊界。

Candidate 必須先過 Geometry Validator

Proposal 產生一個未被其他 node 使用的位置，仍然不代表 layout 合法。

它可能造成：

V3
    moved node lies on a non-incident edge
    or another node now lies on a moved incident edge

V4
    a moved incident edge overlaps another edge

所以一個 proposal 的處理順序是：

propose position
       |
       v
V1 / V2 / V3 / V4 validation
       |
       +---- invalid ----> reject without scoring
       |
       v
crossing evaluation
       |
       v
SA acceptance

Invalid move 沒有任何溫度可以挽救：

candidate.exact_valid != 1
    -> reject

「高溫可以接受較差解」只適用於較差但合法的 objective。它不表示 SA 可以接受違反題目限制的 layout。

Naive 寫法每個 Proposal 做多少工作？

今天故意使用最容易相信的 transaction：

candidate_positions = list(current_positions)
candidate_positions[node] = new_position

if legal(candidate_positions):
    candidate_objective = full_evaluate(candidate_positions)

每一步的主要成本是：

copy all positions
    O(N)

V3 node-on-edge validation
    O(N * E)

V4 overlap validation
    O(E * E)

full crossing evaluation
    O(E * E)

總共執行 S 個 proposals 時，crossing 相關成本大致是：

O(S * E * E)

這非常慢，但狀態管理很乾淨：

reject
    -> throw candidate copy away
    -> current was never modified

accept
    -> replace current with candidate

不需要 rollback，也不需要信任 incremental cache。

這就是 Naive 版本的價值。後面任何 GPU、incremental 或 device-resident 實作，都可以餵入相同 proposals，再和它逐步比較：

valid / invalid
candidate objective
accept probability
random draw
accept / reject branch
current objective after commit
best objective after publication

實際跑一次 Single-Chain SA

範例在：

case_4/examples/sa_naive.py

執行：

python case_4/examples/sa_naive.py --seed 42

預設建立：

16 nodes
28 undirected edges
60 * 60 integer canvas
5,000 proposals
start temperature = 2.0
cooling rate = 0.999

這次固定 seed 的結果是：

initial objective
    (K=13, n_K=1, Phi=1586, C=90)

best objective
    (K=1, n_K=14, Phi=14, C=7)

proposals         = 5,000
legal proposals   = 4,788
accepted          = 504
accepted uphill   = 178
best updates      = 32

K 從 13 降到 1。更能說明 SA 行為的是，它接受了 178 個 stochastic uphill moves，但只發布了 32 次 strictly better best updates。這裡的 uphill 是指進入機率判斷的 acceptance branch，不是拿 strict lexicographic tuple 重新分類。

accepted moves
    maintain exploration state

best updates
    maintain output quality

兩個 counter 衡量的是不同的事情。

目前工作環境的兩次 smoke runs 約為 1.7～2.1 秒。它們沒有 warm-up、足夠的重複樣本、硬體資訊或 confidence interval，不能當成正式 benchmark。

而且這是小圖。若 edges 從 28 增加到 280，單純按照 edge-pair 數量估算，full crossing work 不是增加 10 倍，而是接近：

(280 / 28) * (280 / 28) = 100x

這就是下一篇一定要處理的問題。

Acceptance Rate 高，不代表搜尋有效

假設兩個設定：

setting A
    10,000 proposals
    8,000 accepted
    best K never changes

setting B
    10,000 proposals
    800 accepted
    best K improves five times

只看 acceptance rate，A 看起來非常活躍。但它可能一直接受 objective 幾乎相同的 moves，沒有解開真正的 bottleneck edge。

更有意義的 telemetry 包括：

proposal_count
legal_proposal_count
delta_evaluation_count
accepted_count
accepted_uphill_count
best_update_count
K-improving accepted count
time_to_best_K
proposals_to_best_K

這些數字可以組成一條 funnel：

all proposals
      |
      v
legal proposals
      |
      v
evaluated deltas
      |
      v
accepted moves
      |
      v
best-K improvements

GPU 把第一層 proposal volume 拉高後，如果 legal rate、useful delta rate 或 best-update rate 很低，最後的 K 仍然不會改善。

為什麼 SA 比 Layout 更難直接平行？

Day 25 的 repulsion 可以讓很多 owner nodes 同時計算，因為它們都讀 iteration t 的 positions。

單條 SA chain 卻有真實的時間相依：

proposal at step t
    -> evaluated against current state t
    -> accept or reject
    -> produces current state t + 1

proposal at step t + 1
    -> must use current state t + 1

在 step t 還沒決定前，無法確定 step t + 1 應該從哪一份 layout 出發。

matrix-like independent work
    item 0, item 1, item 2 can run together

single SA chain
    state 0 -> state 1 -> state 2

因此「把 10,000 個 SA steps 各自交給一個 thread」通常是錯的。那些 threads 看到的 current state 不一致，也無法按照正確順序 commit。

GPU 仍然能加速三個地方：

within one proposal
    parallel geometry and crossing delta

within one chain
    keep sequential control on device

across chains or replicas
    evaluate independent current states concurrently

今天只建立第一條 chain 的語意。沒有這份 baseline，後面很難分辨 GPU 版本是加速了相同演算法，還是偷偷改變了接受順序。

這個案例介紹了 GPU 最佳化的哪一部分？

Day 26 還沒有把 SA loop 搬進 GPU，但它先固定了 GPU 化時不能破壞的 state machine：

proposal
    -> legality
    -> objective delta
    -> stochastic acceptance
    -> current commit
    -> best publication
    -> cooling

它也揭露即將出現的系統瓶頸：

CPU creates one proposal
GPU evaluates one proposal
CPU waits for result
CPU decides acceptance
GPU commits or rolls back
repeat thousands of times

即使 crossing kernel 只花幾十 microseconds，每一步的 launch、synchronization 與 host-device control transfer 都可能吃掉大部分時間。

Day 27 會保留同一條 sequential dependency，但把 proposal、delta evaluation、acceptance、current state 與 best state 放進 device-resident loop。重點會是：

如何避免每一步跨過 PCIe / driver boundary
如何讓 rejected move 不必複製整張 layout
如何保存 scratch state 並安全 commit
kernel fusion 為什麼可能比單一 predicate 再快 10% 更重要

程式對照

• Day 26 executable single-chain baseline
• CPU SA lex objective and acceptance
• Flash-SA layered acceptance
• GPU lex objective construction
• Production Flash-SA kernel
• Acceptance differential tests